Теорема о матрице композиции

Пусть $\rho$ и $\sigma$ — бинарные отношения, а $M_{\rho}$ и $M_{\sigma}$ — их булевы матрицы. Тогда матрица композиции отношений $M_{\rho \circ \sigma}$ равна булевому произведению матриц $M_{\rho}M_{\sigma}$: $$M_{\rho \circ \sigma} = M_{\rho}M_{\sigma}$$

Докажем, что элемент $(i,j)$ матрицы $M_{\rho \circ \sigma}$ равен 1 тогда и только тогда, когда элемент $(i,j)$ булева произведения $M_{\rho}M_{\sigma}$ равен 1. По определению матрицы отношения: $$M_{\rho \circ \sigma}[i,j] = 1 \iff (a_i, a_j) \in \rho \circ \sigma$$ По определению композиции отношений: $$\iff \exists{\ell}\mathpunct{:}~~ (a_i, a_{\ell}) \in \rho \text{ и } (a_{\ell}, a_j) \in \sigma$$ По определению матрицы отношения: $$\iff \exists{\ell}\mathpunct{:}~~ M_{\rho}[i,\ell] = 1 \text{ и } M_{\sigma}[\ell,j] = 1$$ Так как $M_{\rho}[i,\ell], M_{\sigma}[\ell,j] \in \{0, 1\}$, их произведение равно 1 тогда и только тогда, когда оба множителя равны 1: $$\iff \exists{\ell}\mathpunct{:}~~ M_{\rho}[i,\ell]M_{\sigma}[\ell,j] = 1$$ По определению булевого умножения матриц: $$\iff (M_{\rho}M_{\sigma})[i,j] = 1$$ Следовательно, $M_{\rho \circ \sigma} = M_{\rho}M_{\sigma}$. $\square$